package stack_queue_1018;

import java.util.Deque;
import java.util.LinkedList;

public class Q2 {
    static class Node {
        int val;
        Node next;

        Node(int val) {
            this.val = val;
            this.next = null;
        }
    }

    // 1 -> 2 -> 3 -> 4
    // 打印 4、3、2、1
    private static void 逆序打印链表版本1(Node head) {
        // 使用栈
        Deque<Integer> stack = new LinkedList<>();
        // 遍历链表，将链表按照从前到后的顺序，进行遍历，将元素压入栈中
        Node cur = head;
        while (cur != null) {
            int e = cur.val;
            // 压栈
            stack.push(e);
            cur = cur.next;
        }

        // 将栈中的所有元素依次弹出并打印，按照先进后出，则逆序打印了链表
        while (!stack.isEmpty()) {
            int e = stack.pop();    // Integer -> int 自动拆箱
            System.out.println(e);
        }
    }

    // 1 -> 2 -> 3 -> 4
    // 打印 4、3、2、1
    private static void 逆序打印链表(Node head) {
        // 利用递归（实际利用的调用栈（调用栈也是栈））完成逆置
        if (head == null) {
            return;
        }

        逆序打印链表(head.next);
        System.out.println(head.val);
    }

    public static void main(String[] args) {
        Node n1 = new Node(100);
        Node n2 = new Node(200);
        Node n3 = new Node(300);
        Node n4 = new Node(400);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = null;

        逆序打印链表(n1);
    }
}
